package com.test.daily.leetcode.y2022.m07.day0704.v07;

/**
 * @author Tom on 2022/7/4
 */
public class Solution {
    public static int maxCoins(int[] arr) {
        int N = arr.length;
        int[] help = new int[N + 2];
        for (int i = 1; i <= N; i++) {
            help[i] = arr[i - 1];
        }
        help[0] = 1;
        help[N + 1] = 1;
        return func(help, 1, N);
    }

    public static int func(int[] help, int L, int R) {
        if (L == R) {
            return help[L - 1] * help[L] * help[R + 1];
        }
        // L位置的气球最后爆
        int max = help[L - 1] * help[L] * help[R + 1] + func(help, L + 1, R);
        // R位置的气球最后爆
        max = Math.max(max, func(help, L, R - 1) + help[L - 1] * help[R] * help[R + 1]);
        // 中间位置的气球最后爆炸
        for (int i = L+1; i < R; i++) {
            int left = func(help, L, i - 1);
            int right = func(help, i + 1, R);
            int mid = help[L - 1] * help[i] * help[R + 1];
            int cur = left + mid + right;
            max = Math.max(max, cur);
        }
        return max;
    }

    public static int maxCoins2(int[] arr) {
        int N = arr.length;
        int[] help = new int[N + 2];
        for(int i = 1; i <= N; i++){
            help[i] = arr[i-1];
        }
        help[0] = 1;
        help[N+1] = 1;
        int[][] dp = new int[N+2][N+2];
        for(int i = 1; i < N+1; i++){
            dp[i][i] = help[i-1]*help[i]*help[i+1];
        }
        for(int left = N; left >=1; left--){
            for(int right = left + 1; right <= N; right++){
                int max = help[left - 1] * help[left] * help[right + 1] + dp[left + 1][right];
                // R位置的气球最后爆
                max = Math.max(max, dp[left][right-1]+ help[left - 1] * help[right] * help[right + 1]);
                // 中间位置的气球最后爆炸
                for (int i = left+1; i < right; i++) {
                    int leftAns = dp[left][i - 1];
                    int rightAns = dp[i + 1][right];
                    int midAns = help[left - 1] * help[i] * help[right + 1];
                    int cur = leftAns + midAns + rightAns;
                    max = Math.max(max, cur);
                }
                dp[left][right] = max;
            }
        }
        return dp[1][N];
    }
}
